1. Field of the Invention
The present invention generally relates to digital communications systems and, more particularly, to a high performance error control coding scheme for channel encoders and decoders that adds redundancy to the data prior to transmission and then decodes the data upon reception in a selective fashion. Such devices for error protection of data are commonly referred to as "channel codecs" for channel coding and channel decoding. The invention has particular application in digital cellular networks but may be advantageously used in any product line that employ low rate voice codecs and require error control for compressed speech data.
2. Description of the Prior Art
Cellular telecommunications systems are evolving from their current analog frequency modulated (FM) form towards digital systems. The Telecommunication Industry Association (TIA) has adopted a standard that uses a full rate 8.0 Kbps Vector Sum Excited Linear Prediction (VSELP) speech coder, convolutional coding for error protection, differential quadrature phase shift keying (QPSK) modulation, and a time division, multiple access (TDMA) scheme employing a 40 ms frame subdivided into six time slots per carrier frequency. The full rate standard occupies two time slots per 40 ms and is thus expected to triple the traffic carrying capacity of the cellular systems.
In order to further increase its capacity by a factor of two, the TIA has begun the process of evaluating and subsequently selecting a half rate speech and channel codec that would only require one time slot per 40 ms. For the purposes of the TIA half rate codec selection, the half rate speech plus channel codec should have an overall bit rate of 6.5 Kbps and is restricted to a frame size of 40 ms. The half rate speech plus channel codec is expected to have a voice quality comparable to the full rate standard over a wide variety of conditions. These conditions include various speakers, influence of handsets, background noise conditions, and channel conditions.
The error protection scheme used in the full rate standard utilizes the well known half rate convolutional channel encoder. The half rate convolutional channel encoder adds redundancy to the compressed speech data by using a shift register, generating two output bits for every input bit, and multiplexing the output bits to form the output. The generation of each output bit is done by a weighted modulo 2 sum of the input bit and the shift register contents according to a predefined generator polynomial. The number of memory elements in the shift register plus one is referred to as the constraint length of the convolutional coder. In the case of the full rate standard, there is a constraint length of six or five memory elements. The initial state of the shift register is zeroed out, and the final state is also guaranteed to be zero by flushing it with five tail or flush bits of "0" after every input block of compressed speech data.
The VSELP speech codec puts out 159 compressed speech bits every 20 ms. These bits are divided into two classes. Class 1 bits are bits that are perceptually more significant and therefore require error protection. This is accomplished by the half rate convolutional channel codec with constraint length 6. Class 2 bits are bits that are not as significant as their Class 1 counterparts and are given no error protection. There are 77 Class 1 bits and 82 Class 2 bits. Among the Class 1 bits, there are a few bits that are perceptually the most significant, and it is important that they have error detection capability as well. This is accomplished by using a 7-bit cyclic redundancy check (CRC) over the twelve most perceptually significant bits. The 77 Class 1 bits, the 7 CRC bits, and the 5 tail bits are fed into the convolutional encoder to generate 178 coded bits. These are then fed along with the Class 2 bits into an interleaving array of dimension 26.times.10, interleaved row-wise with the interleaving array of the previous 20 ms frame, and transmitted row-wise after interleaving.
At the receiving station, de-interleaving is first accomplished to yield the 26.times.10 array of coded Class 1 and Class 2 bits of the previous 20 ms VSELP frame. After extracting the 178 coded Class 1 bits, the 77 Class 1 bits and 7 CRC bits are decoded using the Viterbi algorithm, which is a special case of dynamic programming. The locally generated 7 CRC bits are compared to the received 7 CRC bits to provide a bad frame indication to the VSELP speech decoder.
The half rate speech plus channel codec is expected to perform as well as the full rate standard over a variety of channel conditions up to and including 3% bit error rate (BER) at a vehicle speed of 5 mph. The half rate speech codec compressed data carries the same information in approximately half the number of bits per second. As a result, it can be expected to be more sensitive to bit errors on the average. The half rate channel codec would therefore have to provide a greater degree of error protection despite the lower bit rate than the full rate channel codec. This can only be accomplished by a channel codec with a higher degree of error correction capability and which is better tailored to correct the kind of error patterns representative of a Rayleigh fading channel. The convolutional channel codec used in the full rate standard is not tailored in any way to correct transmission errors due to a Rayleigh fading channel. Its error correcting capacity can be increased by increasing its constraint length, but this comes with an exponential increase in cost or complexity of the Viterbi decoder. Generalized Viterbi decoding techniques suffer from the same disadvantages.
Among alternative channel codecs that could be considered for this are short block codes. Such channel codecs also utilize maximum likelihood techniques using soft decision like the convolutional channel decoder. In addition, such channel codecs offer the following additional advantages:
1. No overhead due to flush bits. PA0 2. The codeword generator matrix can be optimized to reduce the average number of bits in error for a given codeword error rate. PA0 3. The interleaver can be optimized for the given fading channel. PA0 4. Generalized decoding can be used to further reduce error rate and bit error rate with little extra cost.
The error correcting power of such block codes is a function of their minimum Hamming distance. Typically, longer block codes possess a larger minimum Hamming distance, but the cost of decoding such block codes also increases with its length, as does the complexity of decoding such block codes. The rate 1/2 nonlinear block code (NBC) discovered by Nordstrom and Robinson (A. W. Nordstrom and J. P. Robinson, Information and Control, November-December 1967, pp. 613-161) of length 16 and minimum Hamming distance 6 appears to be an ideal compromise and has the additional advantage that one can simplify the maximum likelihood decoding using a fast Hadamard transform based method.
The NBC code has been known over two decades. This code is optimal in terms of having the largest number of codewords possible for the given Hamming distance. Despite its optimality, this code has not received much attention in engineering circles because it is nonlinear. Recent results have shown that the NBC code is in fact linear when considered as quaternary (alphabet {0,1,2,3}) codes. As a result, all linear techniques can now be applied to the NBC.